package com.li.sort.arithmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class BucketSort {
	public static final int SIZE = 10000000;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}

		//System.out.println(Arrays.toString(array));
		long time1= System.currentTimeMillis();
		bucketSort(array);
		//System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
	}

	/**
	 * n-1趟排序就ok
	 * @param array
	 */
	public static void bucketSort(int[] array){
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		for(int i=0;i<array.length;i++){
			max = Math.max(max, array[i]);
			min = Math.min(min, array[i]);
		}
		
		int bucketNum = (max - min)/array.length+1;
		bucketNum = 10000;
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		for(int i =0;i < bucketNum;i++){
			list.add(new ArrayList<Integer>());
		}
		
		for(int i=0;i<array.length;i++){
			int num = (array[i]-min) /array.length;
			list.get(num).add(array[i]);
		}
		int index=0;
		for(int i=0;i<list.size();i++){
			Collections.sort(list.get(i));
			for(int j=0;j<list.get(i).size();j++){
				array[index++] = list.get(i).get(j);
			}
		}
	}

	public static void swap(int[] array,int i,int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
